package com.leetcode.partition16;

import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/10/9 19:51
 */
public class LC1584连接所有点的最小费用 {

    public static int minCostConnectPoints(int[][] points) {
        return kruskal(points);
    }

    public static void main(String[] args) {
        int[][] points = {{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}};
        System.out.println(minCostConnectPoints(points));
    }

    private static int kruskal(int[][] points) {
        int answer = 0;
        int[] ancestors = new int[points.length];
        //并查集初始化
        for (int i = 0; i < ancestors.length; i++) ancestors[i] = i;
        //将points转换为边，一个有n个完全无向图有n*(n-1)/2条边
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < points.length; i++) {
            for (int j = i; j < points.length; j++) {
                //不计算自己到自己
                if (i == j) continue;
                int dis = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                edges.add(new int[]{i, j, dis});
            }
        }
        //根据距离进行排序
        edges.sort((o1, o2) -> Integer.compare(o1[2], o2[2]));
        int selectedCount = 0;
        for (int[] edge : edges) {
            //n个顶点的最小生成树有n-1条边
            if (selectedCount == points.length - 1) break;
            //加入当前最小边会形成环，忽略掉当前边
            if (find(ancestors, edge[0]) == find(ancestors, edge[1])) continue;
            //当前边是合法边，对当前边的点进行union加入到已选集合中
            union(ancestors, edge[0], edge[1]);
            answer += edge[2];
            selectedCount++;
        }
        return answer;
    }

    private static int find(int[] ancestors, int x) {
        if (ancestors[x] != x) ancestors[x] = find(ancestors, ancestors[x]);
        return ancestors[x];
    }

    private static void union(int[] ancestors, int x, int y) {
        int ancestorX = find(ancestors, x), ancestorY = find(ancestors, y);
        if (ancestorX != ancestorY) ancestors[ancestorY] = ancestorX;
    }
}
